Public/private key pairs are commonly used for secure communication and to provide identification. A problem with key pair cryptography is the difficulty of knowing that a particular public key actually corresponds to the party one thinks it does. Two approaches are to use a certificate authority, such as Verisign, or to use a web of trust, as recommended by OpenPGP.
Unfortunately, it is often necessary to change a private/pubic key pair. For example, private keys often need to be revoked, either because they are no longer secret or because they have expired. Most private keys expire after a set period of time, such as one year, because the longer a private key is in use, the greater the chance that it will be compromised. Unfortunately, some uses of the key must survive this change. It is important to maintain the trust relationship associated with the old key when moving to a new key.
One standard approach to changing private keys is to sign a certificate that validates the new key with the old key it replaces. Once the certificate is issued and widely accepted, the old key can be revoked or allowed to expire. This process can be continued in order to issue new private keys over time. A problem with this approach is that the entire future chain of such certificates is vulnerable to the loss of a single private key in the sequence. Should any of the private keys be compromised, the rest of the chain starting at that point is not secure. Note also that this procedure only works as long as the user connects while the old key is still valid.
Another approach is to sign a certificate that validates the new key with a closely held private key. If the signing key is carefully protected, it can be used for a very long time. For example, Verisign's closely held private key has a 30 year lifespan. A problem with this approach is that anyone using it is vulnerable to the signing authority. This authority could raise its price for a new key or could fraudulently issue new private keys. In the event of a dispute over ownership of a resource controlled by the private key, the signing authority would have full control.
What is needed is a system and a method to allow the changing of private keys without the problems described above.